package com.yun.algorithmproblem.leetcode;

import java.util.ArrayList;
import java.util.HashMap;

public class Leetcode2502 {

    public static void main(String[] args) {
        Allocator obj = new Allocator(7);
        System.out.println(obj.allocate(3, 1));
        System.out.println(obj.allocate(5, 2));
        System.out.println(obj.freeMemory(1));
        System.out.println(obj.freeMemory(3));
    }

    static class Allocator {
        static class Node {
            Node prev, next;
            int left, right;
        }

        int n;
        HashMap<Integer, ArrayList<Node>> hm;
        Node head, tail;

        public Allocator(int n) {
            this.n = n;
            hm = new HashMap<>();
            head = new Node();
            tail = new Node();
            head.next = tail;
            tail.prev = head;
            head.right = 0;
            tail.left = n;
        }

        public int allocate(int size, int mID) {
            Node prev = head;
            Node next = head.next;
            while (next.left - prev.right < size) {
                if (next.next == null) {
                    return -1;
                }
                next = next.next;
                prev = prev.next;
            }
            //找到了
            Node curr = new Node();
            curr.left = prev.right;
            curr.right = curr.left + size;
            prev.next = curr;
            curr.prev = prev;
            curr.next = next;
            next.prev = curr;
            hm.computeIfAbsent(mID, k -> new ArrayList<>()).add(curr);
            return curr.left;
        }

        public int freeMemory(int mID) {
            if (!hm.containsKey(mID)) {
                return 0;
            }
            ArrayList<Node> nodes = hm.get(mID);
            int res = 0;
            for (Node node : nodes) {
                res+=node.right-node.left;
                Node prev = node.prev;
                Node next = node.next;
                prev.next = next;
                next.prev = prev;
            }
            hm.remove(mID);
            return res;
        }
    }
}
